package tree

// 给定一个二叉树，判断它是否是高度平衡的二叉树：左树平衡 && 右树平衡 && 左右两边高度<=1
// 返回值:-1表示不平衡, >0代表树的高度
//其实这是已一种自底向上的递归，类似于后序遍历，对于当前遍历的节点，先递归的判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一颗子树是平衡的，
//则返回其高度（高度一定是非负整数），否则返回-1
//时间复杂度:O(n),其中n是二叉树的节点个数，使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)
//空间复杂度：O(n)，其中 nn 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n
func maxBalancedBinaryTreeDepth(root *Node) int {
	//check
	if root == nil {
		return 0 // 高度为0
	}

	left := maxBalancedBinaryTreeDepth(root.Left)
	right := maxBalancedBinaryTreeDepth(root.Right)

	//用-1表示不平衡
	if left == -1 || right == -1 || left-right > 1 || right-left > 1 {
		return -1
	}
	if left > right {
		return left + 1
	}
	return right + 1
}

func IsBalancedBinaryTree(root *Node) bool {
	if maxBalancedBinaryTreeDepth(root) == -1 {
		return false
	}
	return true
}
